package com.topcoder.srm286;

import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class MonomorphicTyper {
	private Pattern FUNCTION = Pattern.compile("([a-zA-Z]+)\\((.*)\\)");
	
	private HashMap<String, String> map;
	
	public String infer(String expression, String[] definitions) {
		map = new HashMap<String, String>();
		for (String def : definitions) {
			String[] temp = def.split(":");
			map.put(temp[0], temp[1]);
		}
		return infer(expression);
	}
	
	private String infer(String expression) {
		Matcher m = FUNCTION.matcher(expression);
		String key = expression;
		if (m.matches()) {
			String params = args(m.group(2), map);
			key = m.group(1) + "(" + params + ")";
		}
		return map.containsKey(key)? map.get(key) : "";
	}
	
	private String args(String args, HashMap<String, String> map) {
		StringBuilder sb = new StringBuilder();
		int bracket = 0;
		int head = 0;
		int i = 0;
		while (i < args.length()) {
			switch (args.charAt(i)) {
			case '(':
				bracket++;
				break;
			case ')':
				bracket--;
				break;
			case ',':
				if (bracket == 0) {
					sb.append(infer(args.substring(head, i)) + ",");
					head = i+1;
				}
				break;
			}
			i++;
		}
		sb.append(infer(args.substring(head)));
		return sb.toString();
	}
}
